#include <stdio.h>
#include <stdlib.h>

// 定义线索化二叉树节点结构体
typedef struct ThreadedTreeNode {
    int data;
    struct ThreadedTreeNode *left;
    struct ThreadedTreeNode *right;
    int leftTag;   // 0: 左指针指向左孩子，1: 左指针指向前驱
    int rightTag;  // 0: 右指针指向右孩子，1: 右指针指向后继
} ThreadedTreeNode;

// 定义原二叉树节点结构体
typedef struct TreeNode {
    int data;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

// 创建新节点
ThreadedTreeNode* createThreadedNode(int data) {
    ThreadedTreeNode *node = (ThreadedTreeNode *)malloc(sizeof(ThreadedTreeNode));
    node->data = data;
    node->left = node->right = NULL;
    node->leftTag = 0;
    node->rightTag = 0;
    return node;
}

// 在中序遍历中查找根节点的位置
int searchInOrder(int inorder[], int start, int end, int value) {
    for (int i = start; i <= end; i++) {
        if (inorder[i] == value) {
            return i;
        }
    }
    return -1;
}

// 构建二叉树的递归函数
TreeNode* buildTree(int preorder[], int inorder[], int inorderStart, int inorderEnd, int *preorderIndex, int size) {
    if (inorderStart > inorderEnd) {
        return NULL;
    }

    // 取出前序遍历的根节点
    int rootValue = preorder[*preorderIndex];
    (*preorderIndex)++;

    // 创建根节点
    TreeNode *root = (TreeNode *)malloc(sizeof(TreeNode));
    root->data = rootValue;
    root->left = root->right = NULL;

    // 在中序遍历中找到根节点的位置
    int inorderIndex = searchInOrder(inorder, inorderStart, inorderEnd, rootValue);

    // 构建左子树和右子树
    root->left = buildTree(preorder, inorder, inorderStart, inorderIndex - 1, preorderIndex, size);
    root->right = buildTree(preorder, inorder, inorderIndex + 1, inorderEnd, preorderIndex, size);

    return root;
}

// 中序遍历并将二叉树进行中序线索化
void inOrderThreaded(TreeNode *root, ThreadedTreeNode **prev) {
    if (root == NULL) {
        return;
    }

    inOrderThreaded(root->left, prev);

    // 将原二叉树节点转换为线索化节点
    ThreadedTreeNode *threadedNode = createThreadedNode(root->data);
    if (*prev != NULL) {
        // 更新前驱节点
        (*prev)->right = threadedNode;
        (*prev)->rightTag = 1;
        threadedNode->left = *prev;
        threadedNode->leftTag = 1;
    }
    *prev = threadedNode;

    inOrderThreaded(root->right, prev);
}

// 中序遍历线索化二叉树
void printInOrderThreaded(ThreadedTreeNode *root) {
    ThreadedTreeNode *current = root;
    while (current != NULL) {
        // 找到最左侧的节点
        while (current->leftTag == 0 && current->left != NULL) {
            current = current->left;
        }
        // 打印当前节点
        printf("%d ", current->data);

        // 移动到后继节点
        while (current->rightTag == 1 && current->right != NULL) {
            current = current->right;
            printf("%d ", current->data);
        }
        current = current->right;
    }
}

// 释放线索化二叉树内存
void freeThreadedTree(ThreadedTreeNode *root) {
    if (root != NULL) {
        if (root->leftTag == 0) {
            freeThreadedTree(root->left);
        }
        if (root->rightTag == 0) {
            freeThreadedTree(root->right);
        }
        free(root);
    }
}

// 释放原始二叉树内存
void freeTree(TreeNode *root) {
    if (root != NULL) {
        freeTree(root->left);
        freeTree(root->right);
        free(root);
    }
}

// 主函数示例
int main() {
    // 示例前序遍历和中序遍历序列
    int preorder[] = {1, 2, 4, 5, 3, 6, 7};
    int inorder[] = {4, 2, 5, 1, 6, 3, 7};
    int size = sizeof(preorder) / sizeof(preorder[0]);

    int preorderIndex = 0;
    TreeNode *root = buildTree(preorder, inorder, 0, size - 1, &preorderIndex, size);

    // 转换为线索化二叉树
    ThreadedTreeNode *threadedRoot = NULL;
    ThreadedTreeNode *prev = NULL;
    inOrderThreaded(root, &prev);
    threadedRoot = prev;

    // 打印中序遍历结果
    printf("线索化二叉树的中序遍历结果: ");
    printInOrderThreaded(threadedRoot);
    printf("\n");

    // 释放内存
    freeThreadedTree(threadedRoot);
    freeTree(root);

    return 0;
}
